package 二叉树.后序遍历.栈方法;



import java.util.*;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }

}

public class Solution {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.right=node2;
        node2.left=node3;
        int[] ints = postorderTraversal(node1);
        System.out.println(ints);
    }

    public static int[] postorderTraversal(TreeNode root) {
        /**
         *  通过先序遍历 把数据 读出来  是 根右左  , 压入栈 为 根 右 左, 出栈为 左 右 根.  这思想牛逼
         */

        if (root == null) {
            return new int[]{};
        }
        TreeNode p = root;

        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> lastStack = new Stack<>();

        stack.push(root);
        while (!stack.isEmpty()){

            TreeNode pop = stack.pop(); // 因为要使压入栈的顺序为 根 右 左  所以要先读根, 再读右, 再度左, 根先进,根出, 左进,右进,右出,左出。
                                        // 根节点始终是最先入栈的。

            lastStack.push(pop.val);

            if (pop.left!=null){
                stack.push(pop.left);
            }
            if (pop.right!=null){
                stack.push(pop.right);
            }


        }


        int size = lastStack.size();

        int[] ints = new int[size];
        for (int i = 0; i < size; i++) {
            ints[i] =lastStack.pop();
        }
        return ints;
    }


}
/**
 * 错误做法:
 *
 * while (p != null || !stack.isEmpty()) {
 *             // 左孩子不为空, 则把左孩子入栈
 *             if (p != null) {
 *                 stack.push(p);
 *                 p = p.left;
 *             } else {
 *                 // 若左孩子为null
 *                 // 查看栈顶元素
 *                 TreeNode peek = stack.peek();
 *                 // 如果该结点 右孩子也为null, 则出栈
 *                 if (peek.right == null) {
 *                     TreeNode pop = stack.pop();
 *                     list.add(pop.val);
 *                     if (!stack.isEmpty()) {
 *                         // 若此时栈内有元素, 则让p指向栈顶元素的右孩子
 *                         p = stack.peek().right;
 *                     } else {
 *                         // 若栈内无元素了, 让p指向空即可.
 *                         p = stack.peek();
 *                     }
 *                 } else {
 *                     // 如果 该结点右孩子不为null, 让p指向栈顶元素的右孩子
 *                     p = peek.right;
 *                 }
 *             }
 *         }
 */